package com.lsa.skienna.challenge.chap8;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BiggerSquare {
	
	private int minimalSquareCount = Integer.MAX_VALUE;
	private Field solution;
	
	static public void main(String[] args) {
	}
	
	Field solve(int size) {
		Field field = new Field(size);
		
		for (int i = size - 1; i > 0; i--) {
			field.lastPlacedSize = i;
			bactrack(field, 1);
		}
		
		return solution;
	}
	
	void bactrack(Field field, int depth) {
		System.out.println(field.toString(depth));
		
		if (isSolution(field)) {
			processSolution(field);
		}
		else {
			if (minimalSquareCount <= field.squareCount() + 1) { // we already have better solutions
				return;
			}
			
			Candidates candidates = constructCandidates(field);
			if (candidates.isolatedSizeOneSquares.size() > 0) {
				field.placeAll(candidates.isolatedSizeOneSquares);
				bactrack(field, ++depth);
				field.unPlaceAll(candidates.isolatedSizeOneSquares);
			}
			else {
				if (field.isCanBePlacedSimulatenously(candidates.otherCandidates)) {
					field.placeAll(candidates.otherCandidates);
					bactrack(field, ++depth);
					field.unPlaceAll(candidates.otherCandidates);
				}
				else {
					Rectangle square = candidates.otherCandidates.get(0);
					field.beginBacktrack(square);
					
					for (Rectangle candidate : candidates.otherCandidates) {
						field.place(candidate);
						bactrack(field, ++depth);
					}
					
					field.endBacktrack();
				}
			}
		}
	}
	
	private Candidates constructCandidates(Field field) {
		List<Rectangle> candidates = new ArrayList<Rectangle>();

		List<Direction> directions = new ArrayList<Direction>();
		directions.addAll(Arrays.asList(Direction.LEFT, Direction.UP, Direction.RIGHT, 
				Direction.RIGHT, Direction.DOWN, Direction.DOWN, Direction.LEFT, 
				Direction.LEFT, Direction.UP));
		
		
		Rectangle candidate = new Rectangle(1, 1, 1, 1);
		 
		List<Rectangle> isolatedSizeOneSquares = new ArrayList<Rectangle>();
		for (int i = 1; i <= field.size; i++) {
			for (int j = 1; j <= field.size; j++) {
				candidate.move(i, j);
				if (!field.isCanBePlaced(candidate)) continue;
				int count = 0;
				int k = 0;
				for (; k < directions.size(); k++) {
					Direction d = directions.get(k);
					candidate.move(d);
					
					boolean isCanBePlaced = field.bounds.contains(candidate.upperLeft()) && field.isCanBePlaced(candidate);
					if (isCanBePlaced) {
						count++;
					}
					if (k > 0 && (k % 2 == 0)) {
						if (count == 3) break;
						count = isCanBePlaced ? 1 : 0;
					}
				}
				
				if (k == directions.size()) { // isolated point
					candidate.move(i, j);
					isolatedSizeOneSquares.add(candidate.clone());
				}
			}
		}
		
		if (isolatedSizeOneSquares.size() == 0) {
			boolean isCandidateFound = false;
			int currentSize = field.lastPlacedSize + 1;
			do {
				currentSize--;
				if (currentSize == 0) {
					break;
				}
				
				candidate = new Rectangle(1, 1, currentSize, currentSize);

				for (int i = 1; i <= field.size - currentSize + 1; i++) {
					for (int j = 1; j <= field.size  - currentSize + 1; j++) {
						candidate.move(i, j);
						if (field.isCanBePlaced(candidate)) {
							candidates.add(candidate.clone());
							isCandidateFound = true;
						}
					}
				}
			}
			while(!isCandidateFound);
		}
		
		Candidates candidatesStruct = new Candidates(isolatedSizeOneSquares, candidates);
		return candidatesStruct;
	}
	
	private static class Candidates{
		List<Rectangle> isolatedSizeOneSquares;
		List<Rectangle> otherCandidates;
		
		Candidates(List<Rectangle> isolatedSizeOneSquares,
				List<Rectangle> otherCandidates) {
			this.isolatedSizeOneSquares = isolatedSizeOneSquares;
			this.otherCandidates = otherCandidates;
		}
	}

	private void processSolution(Field field) {
		if (minimalSquareCount > field.squareCount()) {
			minimalSquareCount = field.squareCount();
			solution = field.clone();
		}
	}


	boolean isSolution(Field field) {
		return field.isFilled();
	}

	static class Field {
		int size;
		int square;
		int filledSquare;
		
		int lastPlacedSize;
		
		Rectangle bounds;
		List<Rectangle> squares = new ArrayList<Rectangle>();
		
		Field(int size) {
			this.size = size;
			square = size * size;
			lastPlacedSize = size - 1;
			bounds = new Rectangle(1, 1, size, size);
		}
		
		public Field clone() {
			Field cloned = new Field(size);
			cloned.squares.addAll(squares); 
			return cloned;
			
		}
		
		public void beginBacktrack(Rectangle square) {
			filledSquare += square.square();
			squares.add(null);
		}
		
		public void place(Rectangle square) {
			lastPlacedSize = square.w;
			squares.set(squares.size() - 1, square);
		}
		
		public boolean isCanBePlacedSimulatenously(List<Rectangle> squares) {
			Field clone = this.clone();
			for (Rectangle square : squares) {
				if (clone.isCanBePlaced(square)) {
					clone.squares.add(square);
				}
				else {
					return false;
				}
			}
			return true;
		}
		
		public void placeAll(List<Rectangle> squares) {
			Rectangle rectangle = squares.get(0);
//			lastPlacedSize = squares.get(0).w;
			filledSquare += rectangle.square() * squares.size();
			this.squares.addAll(squares);
		}
		
		public void unPlaceAll(List<Rectangle> squares) {
			for (Rectangle rectangle : squares) {
				filledSquare -= rectangle.square();
				this.squares.remove(this.squares.size() - 1);
			}
		}
		
		public void endBacktrack() {
			if (squares.size() > 0) {
				int index = squares.size() - 1;
				Rectangle square = squares.get(index);
				if (square != null) {
					filledSquare -= square.square();
				}
				squares.remove(index);
			}
		}
		
		int squareCount() {
			return squares.size();
		}
		
		boolean isFilled() {
			return square == filledSquare;
		}
		
		boolean isCanBePlaced(Rectangle square) {
//			List<Point> someVerteces = square.vertecesExceptUpperLeft();
//			for (Point vertex : someVerteces) {
//				if (!bounds.contains(vertex)) {
//					return false;
//				}
//			}
			
			if (filledSquare + square.square() > this.square) {
				return false;
			}
			
			for (Rectangle placedSquare : squares) {
				if (placedSquare.touches(square)) {
					return false;
				}
			}
			
			return true;
		}

		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			String[][] image = new String[size][size];
			for (int i = 1; i <= size; i++) {
				for (int j = 1; j <= size; j++) {
					image[i - 1][j - 1] = "00 ";
				}
			}
			
			for (int i = 1; i <= size; i++) {
				for (int j = 1; j <= size; j++) {
					Point p = new Point(i,j);
					for (int index = 0; index < squares.size(); index++) {
						Rectangle square = squares.get(index);
						if (square.contains(p)) {
							image[i - 1][j - 1] = String.format("%02d ", index + 1);
						}
					}
				}
			}
			
			for (int i = 1; i <= size; i++) {
				for (int j = 1; j <= size; j++) {
					sb.append(image[i - 1][j - 1]);
				}
				sb.append("\r\n");
			}
			
			return sb.toString();
		}
		
		public String toString(int depth) {
			StringBuilder sb = new StringBuilder();
			String[][] image = new String[size][size];
			for (int i = 1; i <= size; i++) {
				for (int j = 1; j <= size; j++) {
					image[i - 1][j - 1] = "00 ";
				}
			}
			
			for (int i = 1; i <= size; i++) {
				for (int j = 1; j <= size; j++) {
					Point p = new Point(i,j);
					for (int index = 0; index < squares.size(); index++) {
						Rectangle square = squares.get(index);
						if (square.contains(p)) {
							image[i - 1][j - 1] = String.format("%02d ", index + 1);
						}
					}
				}
			}
			
			for (int i = 1; i <= size; i++) {
				for (int j = 1; j <= size; j++) {
					String stuffing = "";
					if (j == 1) {
						for (int k = 0; k < depth; k++) {
							stuffing += " ";
						}
					}
					sb.append(stuffing + image[i - 1][j - 1]);
				}
				sb.append("\r\n");
			}
			
			return sb.toString();
		}
	}
	
	static class Point {
		int x;
		int y;
		
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static enum Direction {
		UP,RIGHT,DOWN,LEFT
	}
	
	static class Rectangle{
		private int x;
		private int y;
		private int w;
		private int h;
		
		Rectangle(int x, int y, int w, int h) {
			this.x = x;
			this.y = y;
			this.w = w;
			this.h = h;
		}
		
		public Rectangle clone() {
			return new Rectangle(x, y, w, h);
		}
		
		int square() {
			return w * h;
		}
		
		void move(Direction direction) {
			int dx = 0;
			int dy = 0;
			switch (direction) {
			case UP:
				dy--;
				break;
			case RIGHT:
				dx++;
				break;
			case DOWN:
				dy++;
				break;
			case LEFT:
				dx--;
				break;
			default:
				break;
			}
			x += dx;
			y += dy;
		}
		
		void move(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		List<Point> verteces() {
			return Arrays.asList(new Point(x, y), new Point(x + w - 1, y),
					new Point(x, y + h - 1), new Point(x + w - 1, y + h - 1));
		}
		
		List<Point> vertecesExceptUpperLeft() {
			return Arrays.asList(new Point(x + w - 1, y),
					new Point(x, y + h - 1), new Point(x + w - 1, y + h - 1));
		}
		
		Point upperLeft() {
			return new Point(x, y);
		}
		
		boolean contains(Point p) {
			return this.x <= p.x && this.y <= p.y && this.x + w > p.x && this.y + h > p.y;
		}
		
		boolean touches(Rectangle r) {
			List<Point> otherVertices = r.verteces();
			for (Point otherVertex : otherVertices) {
				if (contains(otherVertex)) {
					return true;
				}
			}
			
			List<Point> verteces = verteces();
			for (Point vertex : verteces) {
				if (r.contains(vertex)) {
					return true;
				}
			}
			
			return false;
		}

		@Override
		public String toString() {
			return " [x=" + x + ", y=" + y + ", w=" + w + ", h=" + h
					+ "]";
		}
	}
	
	static class TaskReader{
		private BufferedReader reader;
		
		TaskReader(InputStream stream) {
			this.reader = new BufferedReader(new InputStreamReader(stream));
		}
		
		Task readNextTask() throws IOException{
			Task task = new Task();
			
			Integer testCaseCount = Integer.valueOf(reader.readLine());
			for (int i = 0; i < testCaseCount; i++) {
				task.sizes.add(Integer.valueOf(reader.readLine()));
			}
			
			return task;
		}
	}
	
	static class ResultWriter{
		private static final String lineSeparator = System.getProperty("line.separator");
		
		private BufferedWriter writer;
		ResultWriter(OutputStream stream) {
			this.writer = new BufferedWriter(new OutputStreamWriter(stream));
		}
		
		void write(Field field) throws IOException{
			writer.write( field.squares.size() +  lineSeparator);
			for (Rectangle square : field.squares) {
				writer.write( String.format("%s %s %s%s", square.x, square.y, square.w, lineSeparator));
			}
			writer.flush();
		}
	}
	
	static class Task {
		List<Integer> sizes = new ArrayList<Integer>();
	}
}
